﻿// 321. 棋盘分割.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
/*
https://www.acwing.com/problem/content/323/

将一个 8×8的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，
这样割了 (n−1)次后，连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

1191_1.jpg

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。

现在需要把棋盘按上述规则分割成 n 块矩形棋盘，并使各矩形棋盘总分的均方差最小。

均方差formula.png ，其中平均值lala.png ，xi 为第 i 块矩形棋盘的总分。

请编程对给出的棋盘及 n，求出均方差的最小值。

输入格式
第 1 行为一个整数 n。

第 2
 行至第 9
 行每行为 8
 个小于 100
 的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

输出格式
输出最小均方差值（四舍五入精确到小数点后三位）。

数据范围
1<n<15
输入样例：
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3
输出样例：
1.633
*/

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>


using  namespace std;

const int N = 16;
int n, m = 8;
int s[N][N];
double f[N][N][N][N][N];
double X; 


double get(int x1, int y1, int x2, int y2) {
	double delta = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
	delta = delta - X;
	return delta * delta;
}


double dp(int k, int x1, int y1, int x2, int y2) {
	if (f[k][x1][y1][x2][y2] >= 0) return f[k][x1][y1][x2][y2];
	if (k == n) return f[k][x1][y1][x2][y2] = get(x1, y1, x2, y2);

	double t = 1e9;
	for (int i = x1; i < x2; i++) {
		t = min(t, dp(k + 1, x1, y1, i, y2) + get(i + 1, y1, x2, y2));
		t = min(t, dp(k + 1, i + 1, y1, x2, y2) + get(x1, y1, i, y2));
	}

	for (int i = y1; i < y2; i++) {
		t = min(t, dp(k + 1, x1, y1, x2, i) + get(x1, i + 1, x2, y2));
		t = min(t, dp(k + 1, x1, i + 1, x2, y2) + get(x1, y1, x2, i));
	}
	
	return f[k][x1][y1][x2][y2] = t;
}


int main()
{
	scanf("%d",&n);
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &s[i][j]);

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= m; j++)
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
	memset(f, -1, sizeof f);
	//计算平均x拔
	X = (double)s[m][m] / n;

	//记忆化搜索
	printf("%.3lf\n",sqrt(dp(1,1,1,m,m)/n));
 
	return 0;
}

